const arr = [2, 8, 5, 1, 3, 2, 0]

// function merge_sort(arr) {
//   const len = arr.length
//   if (len <= 1) return arr
//   const mid = len >> 1
//   const l = merge_sort(arr.slice(0, mid))
//   const r = merge_sort(arr.slice(mid))
//   arr = mergeArr(l, r)
//   return arr
// }

// function mergeArr(l, r) {
//   let i = 0, j = 0
//   const len1 = l.length
//   const len2 = r.length
//   let res = []
//   while (i < len1 && j < len2) {
//     if (l[i] < r[j]) {
//       res.push(l[i])
//       i++
//     }
//     else {
//       res.push(r[j])
//       j++
//     }  
//   }

//   if (i === len1) {
//     res = res.concat(r.slice(j, len2))
//   } else {
//     res = res.concat(l.slice(i, len1))
//   }

//   return res
// }

function merge_sort(arr) {
  if (arr.length <= 1) return arr
  const mid = arr.length >> 1
  const l = merge_sort(arr.slice(0, mid))
  const r = merge_sort(arr.slice(mid))
  const res = merge(l, r)
  return res
}

function merge(l, r) {
  const len1 = l.length
  const len2 = r.length
  let arr = []
  let i = j = 0
  while (i < len1 && j < len2) {
    if (l[i] < r[j]) arr.push(l[i++])
    else arr.push(r[j++])
  }
  if (i < len1) arr = arr.concat(l.slice(i))
  else arr = arr.concat(r.slice(j))
  return arr
}

console.log(merge_sort(arr));
